\chapter{语言实现}
\label{chap:impl}

第\ref{chap:design}章介绍了GSL的语言设计，规定了该语言所需要具有的语法和语义规则。其中，语义规则仅在逻辑上对语言做出了规定，并没有指出该以什么样的方式执行语言所描述的替换，如何进行这一替换是语言的实现所需要解决的问题。本章将讨论语言可能的实现方式并具体地给出一种实现，此外还将讨论和语言实现相关的一些技术问题。

\section{运行模式}
\label{sec:run_mode}

\subsection{模式匹配与属性求值的依赖关系}
\label{sec:pat_attr_dep}

\ref{sec:sema}节详细地列出了属性表达式与模式表达式的相关语义规则，为相应语义的实现提供了一定的提示，但仅仅通过这些规则是无法直接得到相应的替换算法的。主要问题在于模式表达式的匹配与属性表达式的求值存在互相依赖关系：要将模式表达式与计算表达式进行匹配，需要通过对属性表达式求值来检查相关约束；然而对属性访问表达式的求值，又需要先得到所涉及的模式表达式与计算表达式的匹配结果。

本文采用的方法为，在匹配结构的同时检查算子约束。匹配程序可以先找到一部分模式表达式与计算表达式的匹配，在需要对属性表达式进行求值时从已匹配的那部分计算表达式中获取属性值。该实现起来相对简单，运行效率也比较高。但该方法存在一个问题，即对属性表达式的定义位置有限制。模式表达式的匹配和其遍历类似，也是使用逆后序。如果一个属性表达式引用的模式表达式在其所处的模式表达式之后，算法便无法获取该模式表达式所对应计算表达式的属性值，因为其还没有被匹配。虽然这样限制了属性表达式的定义位置，但对属性表达式表达能力的影响却很小。设某一约束的等号左右两边共包含属性访问$p_1.l_1, p_2.l_2, \dots, p_n.l_n$，其中$\langle p_1, p_2, \dots, p_n\rangle$是源模式表达式逆后序序列的子序列。如果可以通过等式变换将$p_n.l_n$表达为$f(p_1.l_1, p_2.l_2, \dots, p_{n-1}.l_{n-1})$，那么只要上述属性表达式在$p_n$的$l_n$处定义即可。通过对现有深度学习编译器中替换规则所涉及属性约束的考察，发现这种变换几乎总是可行的。

虽然这一算法对属性表达式的定义位置施加了更多限制，但是在具体使用时并不需要编写者对此作过多考虑。因为深度学习模型的定义过程通常都是按照逆后序来进行的，上述匹配顺序符合深度学习模型编程的习惯；而Python的作用域规则又决定了一个局部变量名只有绑定了某个对象才能被使用。所以只要编写者按照逆后序定义模式，并在一个属性约束含有的前$n-1$个模式表达式都定义后，在第$n$个模式表达式相应位置用前$n-1$个模式定义属性表达式，那么这样的替换规则一定可以被正确执行。为了使编写者尽早知道所编写的规则能否执行，可以在替换前进行语义检查，这方面内容将在\ref{sec:sema_check}中作具体介绍。

\subsection{单输出替换算法}

解决了模式表达式的匹配与属性表达式的求值之间的依赖关系，下面将具体阐述匹配与改写阶段的执行过程。本节仅考虑单个输出的情况，多输出或可变输出将会在\ref{sec:bidir_match}中处理。算法执行过程中，需要维护一个从模式表达式到计算表达式的双射映射$M:\mathcal{P}\to\mathcal{E}$。在匹配过程中，每得到一组$\Gamma\vdash p\simeq e$，就将$\langle p, e\rangle$添加到$M$中。在匹配与改写过程中，如果需要对属性访问$p.l$求值，就需要从$M$中取出对应的$e=M(p)$，然后访问$attr(e)$中名为$l$的属性值（参照规则\ref{rule:ae_access}）。

\begin{algorithm}[tbp]
    \caption{单输出模式的匹配算法}
    \label{alg:single_match}

    \KwData{模式表达式$p$，计算表达式$e$}
    \KwResult{布尔值，表示是否匹配；匹配映射$M$}

    $M\leftarrow \{\}$\;
    \BlankLine

    \SetKwFunction{Match}{Match}
    \SetKwFunction{Evaluate}{Evaluate}
    \Fn{\Match{$p, e, \Gamma$}}{
        \If{$p\in\mathrm{dom}(M)$}{
            \textbf{return}\ $M(p)=e$\;
        }
        \If{$e\in\mathrm{ran}(M)$}{
            \textbf{return}\ \textbf{false}\;
        }
        $n_e\leftarrow |\{e_i\mid e_i\sqsubseteq_i e\}|$\;
        \uIf{$p=\mathtt{Variadic}\ p_f\ S_t\ \langle\rangle\ s\ a$}{
            \If{$e$不为元组}{
                \textbf{return}\ \textbf{false}\;
            }
            \For{$i\in 1..n_e$}{
                $p_i, f_i\leftarrow\texttt{Instantiate}(p_f, S_t)$\;
                \If{$\neg\ $\Match{$p_i, e_i, \Gamma[s\mapsto i])$}其中$e_i\sqsubset_i e$}{
                    \textbf{return}\ \textbf{false}\;
                }
            }
            $p$更新为$\mathtt{Variadic}\ p_f\ S_t\ \langle f_1, f_2, \dots, f_n\rangle\ s\ a$\;
        }
        \uElseIf{$p=\mathtt{Inst}\ (\mathtt{Variadic}\ p_f\ S_t\ \langle f_1, f_2, \dots, f_n\rangle\ s\ a_l)\ p_t\ a$}{
            $i\leftarrow\ $\Evaluate{$a, \Gamma$}\;
            \textbf{return}\ \Match{$f_i(p_t), e, \Gamma$}\;
        }
        \Else{
            \If{$p$与$e$类型不匹配}{
                \textbf{return}\ \textbf{false}\;
            }
            $n_p\leftarrow |\{p_i\mid p_i\sqsubseteq_i p\}|$\;
            \If{$n_p\neq n_e$}{
                \textbf{return}\ \textbf{false}\;
            }
            \For{$i\in 1..n_p$}{
                \If{$\neg$\ \Match{$p_i, e_i, \Gamma$}其中$p_i\sqsubset_i p, e_i\sqsubset_i e$}{
                    \textbf{return}\ \textbf{false}\;
                }
            }
            \ForEach{$\langle l, a\rangle\in attr(p)$}{
                \If{$\neg(\Gamma\vdash a\cong e.l)$}{
                    \textbf{return}\ \textbf{false}\;
                }
            }
        }
        $M\leftarrow M[p\mapsto e]$\;
        \textbf{return}\ \textbf{true}\;
    }
    \BlankLine

    \Match{$p, e, \{\}$}\;
\end{algorithm}

算法\ref{alg:single_match}展示了将一对模式表达式与计算表达式进行匹配的算法，其基本思路是沿着边的反向进行逐个顶点的匹配。\Evaluate{$a, \Gamma$}表示使用图\ref{fig:attr_eval}中的规则在环境$\Gamma$中求出属性表达式$a$的值。表达式求值与匹配可以直接根据相关规则实现算法，本节不再介绍其具体算法。该算法中既包含常规表达式的一般匹配模式，也包括了对于可变模式和实例访问的特别处理。在该算法中，认为可变模式表达式自身是可变的，在具体化后其自身存储了对应的模板-实例映射，这样实例访问模式也能直接从其指向的可变模式获得对应的实例。\Match 函数可以判断一组$\langle p, e\rangle$在环境$\Gamma$下是否匹配，使用该函数可以在一个计算表达式中搜索匹配的子表达式。方法是对计算表达式$e$作逆后序遍历，对每一个$e_0\subseteq e$，尝试\Match{$p, e_0, \{\}$}直到找到一组对应的匹配。

限于篇幅，算法\ref{alg:single_match}在执行\Match 后省略了一个步骤，即检查所有已匹配非输入输出计算表达式的后继是否也均已匹配，这是定义\ref{def:subst}中对于图替换$\tau$中$f$的第4个条件所要求的。不满足该条件，则不能成为一个合法的匹配。

表达式的改写过程较为直接，通过图\ref{fig:pat_map}中的规则将模式表达式映射为计算表达式，然后将匹配计算表达式对应位置替换成新的表达式即可。在此过程中如果需要访问已匹配的表达式（规则\ref{rule:pe_match}），直接在匹配过程中所得映射$M$中查找即可。

\section{双向匹配算法}
\label{sec:bidir_match}

\ref{sec:run_mode}节中描述了单输出模式匹配的算法，然而GSL所支持的模式还包括了多输出和可变输出模式，目前的匹配算法不足以完成这些模式的匹配。本节中，针对这两类模式，提出了一种双向匹配算法，能够高效地完成这两类模式的匹配。在\ref{sec:multi_match}节中先对多输出模式的双向匹配算法进行介绍，然后在\ref{sec:variadic_match}节中将该算法作一定的修改，使之能用于可变模式的匹配。本节中主要关注图的结构，而不关心具体的表达式形式，所以本节中的算法均使用图的形式描述，其表达式形式可以根据表达式与图的对应关系$\mathscr{F}$和$\mathscr{G}$进行转换。

\subsection{多输出模式匹配}
\label{sec:multi_match}

设计算图$G_e=(V_e, E_e)$的输出顶点为$v^o_e$，模式图的$G_p=(V_p, E_p)$的输出顶点序列为$\mathbf{v}^o_p=\langle v^o_{p, 1}, v^o_{p, 2}, \dots, v^o_{p, n}\rangle$。要对多个输出顶点子图的进行匹配，一种朴素的方法是按照输出模式顶点的顺序依次从计算图中中寻找匹配的顶点。这一方法需要对每一个输出模式图的顶点都完整地遍历一遍整个计算图；同时在每一次尝试匹配时，还要备份之前所匹配到的所有计算表达式，才能在失配后还原到匹配前的状态，以准备下一次尝试。该算法的时间复杂度为$\mathcal{O}(|\mathbf{v}^o_p|\cdot(|V_e|+|E_e|)\cdot(|V_p|+|E_p|))$，显然这一方法复杂度过高，在体量大的计算图上会耗费较多时间。

上述方法的主要问题在于每一个输出顶点都需要从计算图的根节点开始尝试匹配。然而定义\ref{def:subst_rule}对源模式图的连通性作出了要求，如果能从计算图中找到匹配的子图，那么各个输出顶点只会在一个局部区域内出现，而不会散布在整个计算图内。例如图\ref{fig:multi_example}中展示了多输出顶点模式匹配的例子，左图为模式图，右图为计算图，右图中与模式图匹配的部分已经用灰色标出。进行匹配时，首先匹配模式图的第一个输出顶点$v_{p,4}$，在计算图中找到对应顶点为$v_{e,4}$。对于模式图的第二个输出顶点$v_{p,5}$，如果按照上述算法，要先排除$v_{e,1}, v_{e,2}, v_{e,4}$，并尝试与$v_{e,3}$和$v_{e,5}$匹配后才能找到正确的匹配$v_{e,5}$。但其实匹配$v_{p,4}$时就已经确定了所匹配子图的大致位置，由于$v_{p,5}$是$v_{p,3}$的第一个后继，$v_{p,3}$是$v_{p,1}$的第二个后继。对应地在计算图中也只需要先访问$v_{e,1}$的第二个后继$v_{e,3}$，然后访问$v_{e,3}$的第一个后继$v_{e,5}$，将$v_{p.5}$与之匹配就能成功。这样就减少了尝试匹配的次数，提高了匹配的效率。

\tikzstyle{vertex} = [circle, draw, minimum size=8mm, inner sep=0pt]
\tikzstyle{marked} = [circle, draw, fill=black!10, minimum size=8mm, inner sep=0pt]

\begin{figure}[htbp]
    \centering
    \begin{subfigure}{0.4\textwidth}
        \parbox[][6cm][c]{\linewidth}{
            \centering
            \begin{tikzpicture}[node distance=0.7cm]
                \node (vp1) [vertex] {$v_{p,1}$};
                \node (vp2) [vertex, below left=of vp1] {$v_{p,2}$};
                \node (vp3) [vertex, below right=of vp1] {$v_{p,3}$};
                \node (vp4) [vertex, below left=of vp2] {$v_{p,4}$};
                \node (vp5) [vertex, below right=of vp2] {$v_{p,5}$};
                \node (vp6) [vertex, below right=of vp3] {$v_{p,6}$};
                \draw [->] (vp1) -- (vp2);
                \draw [->] (vp1) -- (vp3);
                \draw [->] (vp2) -- (vp4);
                \draw [->] (vp3) -- (vp5);
                \draw [->] (vp3) -- (vp6);
            \end{tikzpicture}
        }
        \caption{模式图}
    \end{subfigure}
    \begin{subfigure}{0.5\textwidth}
        \parbox[][6cm][c]{\linewidth}{
            \centering
            \begin{tikzpicture}[node distance=0.7cm]
                \node (ve1) [marked] {$v_{e,1}$};
                \node (ve2) [marked, below left=of ve1] {$v_{e,2}$};
                \node (ve3) [marked, below right=of ve1] {$v_{e,3}$};
                \node (ve4) [marked, below left=of ve2] {$v_{e,4}$};
                \node (ve5) [marked, below right=of ve2] {$v_{e,5}$};
                \node (ve6) [marked, below right=of ve3] {$v_{e,6}$};
                \node (ve7) [vertex, right=of ve6] {$v_{e,7}$};
                \node (ve8) [vertex, below right=of ve4] {$v_{e,8}$};
                \node (ve9) [vertex, below right=of ve5] {$v_{e,9}$};
                \node (ve10) [vertex, below right=of ve8] {$v_{e,10}$};
                \draw [->] (ve1) -- (ve2);
                \draw [->] (ve1) -- (ve3);
                \draw [->] (ve2) -- (ve4);
                \draw [->] (ve3) -- (ve5);
                \draw [->] (ve3) -- (ve6);
                \draw [->] (ve4) -- (ve8);
                \draw [->] (ve5) -- (ve8);
                \draw [->] (ve6) -- (ve9);
                \draw [->] (ve8) -- (ve10);
                \draw [->] (ve9) -- (ve10);
                \draw [->] (ve1) to[out=0, in=135] (ve7);
                \draw [->] (ve7) to[out=-135, in=0] (ve10);
            \end{tikzpicture}
        }
        \caption{计算图}
    \end{subfigure}
    \caption{多输出模式匹配示例}
    \label{fig:multi_example}
\end{figure}

上述示例的分析展示了双向匹配的初步思想，即在找到第一个匹配的输出顶点之后，分别沿着模式图和计算图的边的正向寻找可能的模式图顶点与计算图顶点的匹配，然后沿着边的反向进行真正的匹配。下面的问题就是需要搜索哪些模式图顶点和计算图顶点的组合，才能保证如果存在匹配则一定能找到这对匹配。由于要沿着图的正向搜索以寻找可能的匹配，所以需要研究已匹配的模式图和计算图中顶点的后继序列所满足的必要条件。

首先对模式图顶点的后继序列进行研究，定理\ref{thm:path_fwd}给出了通过已匹配的模式图顶点寻找待匹配输出顶点的方法。

\begin{theorem}
    \label{thm:path_fwd}
    对于模式图$G_p$，在寻找第$k$个输出顶点$v^o_{p,k}$时，一定存在一个已匹配的顶点$v_{p,i}$，它到$v^o_{p,k}$存在一条路径，在这条路径上除了首个顶点外，每个顶点都是其前驱的第一个未匹配的后继。
\end{theorem}

例如图\ref{fig:multi_example}中搜索$v_{p,5}$时从已匹配的$v_{p,1}$开始有路径$v_{p,1}\to v_{p,3}\to v_{p,5}$，其中$v_{p,3}$是$v_{p,1}$第一个未匹配的后继，$v_{p,5}$是$v_{p,3}$第一个未匹配的后继。下面给出定理的证明。

\begin{proof}
    首先对每个模式图输出顶点定义可达顶点序列。输出顶点$v^o_{p,k}$的可达顶点序列$\mathbf{v}^r_{p,k}$为顶点集$R(v^o_{p,k})-\bigcup_{j=1}^{k-1} R(v^o_{p,j})$的一个排列，并规定该排列是$rpo(G_p)$的子序列。这样，$rpo(G)$也能看作是由子序列$\mathbf{v}^r_{p,1},\mathbf{v}^r_{p,2},\dots,\mathbf{v}^r_{p,n}$拼接而成的。

    令$S_k=\left[\bigcup_{j=1}^{k-1} R(v^o_{p,j})\right] \cap R(v^o_{p,k})$，定义\ref{def:subst_rule}规定了$S_k\neq\emptyset$。由于$S_k\subseteq R(v^o_{p,k})$，必然存在至少一条从$v_{p,i}\in S_k$到$v^o_{p,k}$的路径。路径上可能有多个顶点在$S_k$中，仅考虑只含单个在$S_k$中顶点的路径，这样的路径必然存在。该路径上除了首个在$S_k$中的顶点$v_{p,i}$外，其余顶点都在
    \begin{equation}
        R(v^o_{p,k})-S_k = R(v^o_{p,k}) - \left[\bigcup_{j=1}^{k-1} R(v^o_{p,j})\right] \cap R(v^o_{p,k})=R(v^o_{p,k})-\bigcup_{j=1}^{k-1} R(v^o_{p,j})
    \end{equation}
    之中，这说明它们也是$\mathbf{v}^r_{p,k}$中的元素。

    考虑$\mathbf{v}^r_{p,k}$中除了$v^o_{p,k}$外的每个顶点$v_{p,j}$后继的匹配情况。首先，其后继序列中不可能有$\mathbf{v}^r_{p,1},\mathbf{v}^r_{p,2},\dots,\mathbf{v}^r_{p,k-1}$中的元素，否则该顶点可达前$k-1$个输出顶点的某个顶点。然后，其后继序列中必须含有$\mathbf{v}^r_{p,k}$中的元素，否则该顶点不在$R(v^o_{p,k})$中。这些元素必然是顶点后继序列的一个前缀，否则该后继序列就不是$rpo(G)$的子序列。

    对于路径的起始顶点$v_{p,i}\in S_k$而言，其一定有后继在$\mathbf{v}^r_{p,k}$中。由于后继序列是$rpo(G)$的子序列，而图中已匹配的顶点为$\mathbf{v}^r_{p,1},\mathbf{v}^r_{p,2},\dots,\mathbf{v}^r_{p,k-1}$中的顶点，所以其已匹配的后继必然是其后继序列的一个前缀。相应的，其未匹配的后继必然是其后继序列的一个后缀，并且是将$\mathbf{v}^r_{p,k},\mathbf{v}^r_{p,k+1},\dots,\mathbf{v}^r_{p,n}$拼接后序列的子序列，则该后缀的第一个顶点一定在$\mathbf{v}^r_{p,k}$中。

    综上所述，从某个已匹配的顶点$v_{p,i}$出发，对路径上的每一个顶点选择其第一个未匹配的后继，可保证顶点均在$\mathbf{v}^r_{p,k}$中。由于$\mathbf{v}^r_{p,k}$仅包含一个输出顶点即$v^o_{p,k}$，所以最终一定可以到达$v^o_{p,k}$。
\end{proof}

下面考察任一模式图及与之匹配的计算图子图，定理\ref{thm:succ_corres}给出了其对应顶点后继序列之间的关系。

\begin{theorem}
    \label{thm:succ_corres}
    对于模式图$G_p$及与其匹配的计算图子图$G_m$中的任意一组对应顶点$v_p,v_m$满足$v_m=f(v_p)$：如果$v_{p}$是非输入顶点，$succ(v_{p})$与$succ(v_{m})$中对应位置的顶点匹配；如果$v_p$是输入顶点，$succ(v_p)$和与其等长的一个$succ(v_m)$的子序列对应位置顶点匹配。
\end{theorem}

例如图\ref{fig:multi_example}中$v_{p,2}$与$v_{e,2}$，以及$v_{p,3}$与$v_{e,3}$的后继序列对应位置顶点匹配。而$succ(v_{p,1})$比$succ(v_{e,1})$长度少一，其中$v_{p,2}$与$v_{e,2}$匹配，$v_{p,3}$与$v_{e,3}$匹配，而$v_{e,7}$不在匹配的计算图内。下面给出定理的证明。

\begin{proof}
    由于$G_p$和$G_m$匹配，由定义\ref{def:subst}中$f$的第3个条件可知对每一组匹配的顶点$v_{p,k}$和$v_{m,k}$其对应位置的前驱也匹配。所以$rpo(G_e)$与$rpo(G_m)$的对应位置顶点匹配。设$|rpo(G_p)|=|rpo(G_m)|=n$，下面同时对$G_m$与$G_e$顶点的后继序列进行构造，对构造步骤进行归纳证明。

    初始时，对于任意$v_p\in G_p$及$v_m\in G_m$，$succ(v_p)=succ(v_e)=\langle\rangle$，其对应位置顶点匹配。

    在第$k(1\leq k\leq n)$步时，需要将$v_{p,k}$加入到$pred(v_{p,k})$的每个顶点$\langle v_{p,k_1}, v_{p,k_2}, \dots, v_{p,k_m}\rangle$的后继序列中，同时将$v_{e,k}$加入到$pred(v_{e,k})$的每个顶点$\langle v_{m,k_1}, v_{m,k_2}, \dots, v_{m,k_m}\rangle$的后继序列中。考虑任意一组$(v_{p,k_i}, v_{m,k_i})$，它们必然匹配。根据归纳假设，在更新之前$succ(v_{p,k_i})$和$succ(v_{m,k_i})$对应位置顶点匹配，又因为$v_{p,k}$和$v_{m,k}$匹配，所以将$v_{p,k}$追加到$succ(v_{p,k_i})$后，以及将$v_{m,k}$追加到$succ(v_{m,k_i})$后，$succ(v_{p,k_i})$和$succ(v_{m,k_i})$对应位置顶点依然匹配。以此类推，本步更新的所有模式图顶点及对应的匹配计算图顶点后继序列对应位置元素依然匹配，其余未更新顶点保持其原有性质。

    目前已证明模式图$G_p$和匹配子图$G_m$各对应顶点后继序列对应元素位置匹配。$G_p$中各顶点所构造出的后继序列就是其真正的后继序列；由于$f$第4个条件所规定，$G_m$中所有非输入输出顶点的后继必然已匹配，所以所构造后继序列也是其真正的后继序列。但是$G_m$中的输入顶点的后继可能包含非$G_m$中的顶点，这部分顶点无法与$G_p$匹配，故构造过程中不可能追加到$G_m$顶点的后继序列中。但是由于$G_m$是$G_e$的子图，顶点前驱序列保持不变，所以$rpo(G_m)$是$rpo(G_e)$的子序列。对于输入顶点而言在上述过程中所构造出的后继序列也必然是其真正后继序列的子序列。上述定理得证。
\end{proof}

\begin{algorithm}[tbp]
    \caption{多输出顶点的匹配算法}
    \label{alg:multi_match}

    \KwData{模式图$G_p$，计算图$G_e$}
    \KwResult{布尔值，表示是否匹配；匹配映射$M$}

    $M\leftarrow \{\}$\;
    \BlankLine

    \SetKwFunction{PushSucc}{PushSucc}
    \Fn{\PushSucc{$v_p,v_e,S$}}{
        $v_{p,k_1}\leftarrow v_p$的第一个未匹配的后继\;
        $\mathbf{v}_e\leftarrow v_e$的所有未匹配的后继序列$\langle v_{e,k_2}, \dots, v_{e,n_2}\rangle$\;
        \eIf{$v_p$为输入顶点}{
            \ForEach{$v_{e,i}\in rev(\mathbf{v}_e)$}{
                将$\langle v_{p,k_1}, v_{e,i}\rangle$压入$S$\;
            }
        }{
            将$\langle v_{p,k_1}, v_{e,k_2}\rangle$压入$S$\;
        }
    }
    \BlankLine

    \SetKwFunction{MatchMultiple}{MatchMultiple}
    \Fn{\MatchMultiple{$G_p, G_e$}}{
    $v^o_{e,1}\leftarrow$寻找$G_e$中$v^o_{p,1}$的匹配\;
    \lIf{$v^o_{e,1}$不存在}{\textbf{return}\ \textbf{false}}
    \For{$v^o_{p,j}\in \mathbf{v}^o_p-\{v^o_{p,1}\}$}{
    $S\leftarrow$空栈\;
    \ForEach{$\langle v_p, v_e\rangle \in M$}{
        \PushSucc{$v_p, v_e, S$}\;
    }
    $matched\leftarrow \mathbf{false}$\;
    \While{$S$非空}{
    $\langle v_p,v_e\rangle\leftarrow$从$S$弹出\;
    \If{$v_p\neq v^o_{p,i}$}{
    \PushSucc{$v_p, v_e, S$}\;
    \textbf{continue}\;
    }
    $M\prime\leftarrow M$\;
    $matched, M\leftarrow\ $将$v_p$与$v_e$进行匹配\;
    \uIf{$\neg matched$}{
        $M\leftarrow M\prime$\;
        \textbf{continue}\;
    }\lElse{\textbf{break}}
    }
    \lIf{$\neg matched$}{
        \textbf{return}\ \textbf{false}
    }
    }
    \textbf{return}\ \textbf{true}\;
    }
    \BlankLine

    \MatchMultiple{$G_p, G_e$}\;
\end{algorithm}

结合上述分析，算法\ref{alg:multi_match}描述了多输出顶点模式匹配的具体算法，在算法中对可能匹配的模式图顶点与计算图顶点对进行深度优先搜索，需要一个栈存储可能的匹配对。\PushSucc 函数将一对$\langle v_p, v_e\rangle$可能涉及的后继匹配组压入栈$S$中，其中$rev(\mathbf{v}_e)$表示将序列$\mathbf{v}_e$的元素进行反向迭代，这是为了使得从栈中弹出时能维持$\mathbf{v}_e$的顺序。\textbf{while}循环中尝试匹配前需要先备份已有的映射，单输出顶点的匹配算法见算法\ref{alg:single_match}，该算法同时得到布尔值以及顶点映射。和单输出匹配算法类似，多输出算法的最后也需要检查每个已匹配的非输入输出计算图顶点的后继是否均已匹配。

该算法只需要对整个计算图进行一次完整的遍历。算法的时间复杂度和计算图规模呈线性关系，比例系数应为一常数，和模式图规模无关。在匹配第一个顶点后，进行$|\mathbf{v}^o_p|-1$次迭代。对单个模式图输出顶点的前向搜索过程中，最多需要遍历整个模式图能够找到输出顶点。计算图的对应搜索过程可能涉及匹配子图的输入顶点，这时需要将计算图中对应顶点所有的后继都进行搜索。最坏情况下可能要访问计算图的所有顶点和边，此时一次循环的时间复杂度达到$\mathcal{O}(|V_e|+|E_e|)$。但现实中的计算图不会出现此类情况，任何顶点的后继数量不会随着模型的规模增大而无限制地增大。因此所搜索的计算图规模应该为模式图规模的常数倍，为$\mathcal{O}(|V_p|+|E_p|)$。所以时间复杂度中和模式图相关的部分为$|\mathbf{v}^o_p|\cdot(|V_p|+|E_p|)$，相对模式图的整体规模介于线性和平方之间。由上述分析可知，该算法总体的平均时间复杂度为
\begin{equation}
    \label{eq:time_complexity}
    \mathcal{O}(|V_e|+|E_e|+|\mathbf{v}^o_p|\cdot(|V_p|+|E_p|))
\end{equation}
在得到第一个匹配后，可以根据需要停止匹配或继续寻找其余匹配。如果对计算图中所有的子图均进行匹配，其时间复杂度和单次匹配会有所差异，在\ref{sec:alg_test}中将会通过实验考察这种情况下算法的时间复杂度。

\subsection{可变输出模式匹配}
\label{sec:variadic_match}

在设计了多输出模式的匹配算法后，下面来考虑可变输出模式的匹配算法。可变输出模式和多输出模式存在一定的差异。可变模式的模式图在定义时只包含一个单独的输出顶点，该输出顶点是可变模式的一个分支。真正与计算图进行匹配的，是通过实例化算法生成的模式图顶点。在匹配策略上，可变模式匹配算法应尽可能多地找到和模式输出顶点匹配的计算图顶点，所匹配计算图顶点的具体数目在匹配前是未知的。

\begin{figure}[htbp]
    \centering
    \begin{subfigure}{0.4\textwidth}
        \parbox[][5.3cm][c]{\linewidth}{
            \centering
            \begin{tikzpicture}[node distance=0.7cm]
                \node (vp1) [vertex] {$v_{p,1}$};
                \node (vp2) [vertex, below=of vp1] {$v_{p,2}$};
                \node (vp3) [vertex, below=of vp2] {$v_{p,3}$};
                \draw [->] (vp1) -- (vp2);
                \draw [->] (vp2) -- (vp3);
            \end{tikzpicture}
        }
        \caption{模式图}
    \end{subfigure}
    \begin{subfigure}{0.5\textwidth}
        \parbox[][5.3cm][c]{\linewidth}{
            \centering
            % \begin{tikzpicture}
            %     \matrix [row sep=6mm,column sep=6mm] {
            %         & \node (ve1) [marked] {$v_{e,1}$}; & \\
            %         \node (ve2) [marked] {$v_{e,2}$}; &
            %         \node (ve3) [marked] {$v_{e,3}$}; &
            %         \node (ve4) [marked] {$v_{e,4}$}; &
            %         \node (ve5) [vertex] {$v_{e,5}$}; \\
            %         \node (ve6) [marked] {$v_{e,6}$}; &
            %         \node (ve7) [marked] {$v_{e,7}$}; &
            %         \node (ve8) [marked] {$v_{e,8}$}; \\
            %         & \node (ve9) [vertex] {$v_{e,9}$}; \\
            %     };
            %     \draw [->] (ve1) -- (ve2);
            %     \draw [->] (ve1) -- (ve3);
            %     \draw [->] (ve1) -- (ve4);
            %     \draw [->] (ve1) -- (ve5);
            %     \draw [->] (ve2) -- (ve6);
            %     \draw [->] (ve3) -- (ve7);
            %     \draw [->] (ve4) -- (ve8);
            %     \draw [->] (ve6) -- (ve9);
            %     \draw [->] (ve7) -- (ve9);
            %     \draw [->] (ve8) -- (ve9);
            %     \draw [->] (ve5) to[out=-90, in=0] (ve9);
            % \end{tikzpicture}
        }
        \caption{计算图}
    \end{subfigure}
    \caption{可变输出模式匹配示例}
    \label{fig:var_example}
\end{figure}

图\ref{fig:var_example}展示了一个可变输出的模式的匹配示例，左图为模式图，右侧为计算图，可变模式在计算图中的匹配顶点用灰色标示。其中$v_{p,1}$为公共的输入顶点，$v_{p,2}, v_{p,3}$为各个分支独有的顶点。计算图中有一个含有三个输出顶点的子图与之匹配。$v_{e,1}$虽然还有一个后继$v_{e,5}$，但由于$v_{p,3}$并不与$v_{e,9}$匹配，所以不能包括在所匹配的计算图子图中。

可变输出模式的匹配与多输出模式的匹配在算法流程上比较接近，其区别主要在于：在尝试匹配输出顶点前，要先将模板实例化，如果失配，需要将该次实例化的模式实例撤销。首次匹配成功后，如果在后续匹配更多输出顶点过程中，经过一轮搜索无法找到合适的匹配，则算法结束，但匹配依然是成功的。在搜索过程中，对于模式图顶点只需要访问第一个后继，而非第一个未匹配的后继。由于和多输出模式的匹配算法接近，本文将不再给出其具体算法。多输出模式的匹配算法可见算法\ref{alg:multi_match}，模板的实例化与可变模式的具体化可参考算法\ref{alg:single_match}中对可变模式的处理。

可变输出模式的时间复杂度较难给出其阶的估计，因为其输出顶点数依赖于计算图的结构。在\ref{sec:alg_test}节中，将会通过实验对可变输出模式的时间复杂度进行考察。

\section{语义检查}
\label{sec:sema_check}

\ref{sec:run_mode}节与\ref{sec:bidir_match}节已经介绍了执行一个GSL定义的计算图替换所需的所有核心算法。但是用户编写的程序可能存在各种各样语义上的错误，导致替换无法正确执行。如果只在执行遇到错误时才报告给用户，由于用户并不了解算法的具体细节，可能导致其无法准确定位产生错误的位置，难以修改其程序。所以对程序进行静态的语义检查，将运行时可能出现的错误尽可能早地暴露出来，是有必要的。本节将讨论语义检查所涉及的内容以及检查方法。

一个替换规则要是可执行的，其包含的每一个模式表达式与属性表达式自身首先要合法的。这一步检查在用户调用API定义表达式AST的过程中就可以检查。比如对于算子调用模式，需要检查算子是否存在、输入数据个数是否正确、属性名称是否合法等。如果检查到非法的表达式，应该在其构造函数中就将其检查出来并报告给用户，使用户可以第一时间定位错误并修改。

此外，还需要检查上下文是否合法。其中一些来自语言本身的语义定义，比如对于对于属性表达式中的符号$s$，要检查其是否在环境$\Gamma$中。另外一些来自语言的运行模式所增加的额外要求，比如对于属性访问$p.l$，按照\ref{sec:pat_attr_dep}节的方法，要检查对该属性表达式求值时$p$是否已经匹配过。要检查此类属性，可以在语义检查时维护一个假的上下文，按照实际执行时的顺序遍历模式表达式与属性表达式。在遇到相应表达式时，检查在上下文中是否存在所要查找的条目。

最后，还需要检查模式图在结构上的合法性，比如源模式图需要为连通图，目标模式图只能包含源模式图中定义的输入顶点。此类约束，需要在语义检查时记录访问过的所有顶点集合，借助集合的相关运算来进行检查。

在进行检查的过程中，还可以构造一些匹配所需要的辅助结构。比如后继序列就是在进行语义检查的时候所构建的，因为后继序列要求通过逆后序遍历模式图，而用户定义模式表达式的时候不一定严格按照逆后序。如果在用户定义表达式时就构建后继序列，所构建的序列可能不合法。

% \section{参数折叠}
% \label{sec:param_fold}

% 提升网络的运行效率是进行图替换的目的之一，但仅仅进行图替换本身有时并不一定能提升运行效率。图替换有时可以将网络中可以预计算的参数暴露出来，进行预计算之后，才可以节省在运行时计算或存储资源。本文中将这种通过对模型参数预计算来对工作负载进行的变换称为参数折叠。

% \begin{figure}[htbp]
%     \centering
%     \begin{subfigure}{\linewidth}
%         \centering
%         \includegraphics[width=9cm]{conv_bn.pdf}
%         \caption{原始计算图}
%     \end{subfigure}
%     \begin{subfigure}{\linewidth}
%         \centering
%         \includegraphics[width=8cm]{conv_bn_subst.pdf}
%         \caption{替换后计算图}
%     \end{subfigure}
%     \begin{subfigure}{\linewidth}
%         \centering
%         \includegraphics[width=6cm]{conv_bn_fold.pdf}
%         \caption{参数折叠后计算图}
%     \end{subfigure}
%     \caption{参数折叠实例}
%     \label{fig:fold_example}
% \end{figure}

% 图\ref{fig:fold_example}中将用于推理的、含有卷积-批归一化这一模式的计算图进行替换，其中$\texttt{\%}l$表示名称为$l$的变量。计算图中只有\texttt{\%x}为输入数据，其余均为模型参数。在进行图替换后，可以看到其变成了一个更复杂的计算图。通过观察可以发现，计算图中除了二维卷积（\texttt{nn.conv2d}）以及偏置加（\texttt{nn.bias\_add}）之外其余的顶点的结果都可以在编译期计算得到，这意味着这些顶点都可以进行参数折叠。参数折叠后，计算图只含有两个算子调用顶点。由于偏置加运算计算量小于批归一化，网络的整体推理性可以得到提升。

% 参数折叠和常规编译优化中的常量折叠非常类似，都是在编译时预先执行程序中不依赖输入的计算，以提升程序的运行性能。和常量折叠仅预计算常量表达式不同，参数折叠可以把模型参数也纳入计算范围，而不仅仅只是网络中的常量。由于参数折叠同时改变了网络结构以及模型参数，所以一个参数折叠程序是一个对工作负载的变换。

% 参数折叠的流程遵循算法\ref{alg:rev_post}的基本框架，对计算图进行逆后序遍历。对每一个算子调用顶点，检查其前驱在变换后是否均为常量或变量。如果不满足，则不处理该顶点。如果满足，则将其前驱对应的值取出。常量的值存储在顶点内，变量需要到模型的参数列表$\Theta$中去寻找对应的值。然后按照算子的名称以及算子调用的属性，对参数进行预计算。最后构造一个新的变量替代原来的算子调用，然后将计算出来的张量值插入参数列表中该变量所对应的位置即可。

% 在具体实现中，算子的计算可以调用现有的数值计算库，如NumPy\cite{harris2020array}等。此外，图替换所变换的计算图中的算子，与参数折叠所调用的数值计算库的算子，两者语义可能有所差异。因此，参数折叠程序应该能够注意到这种差异，正确地进行属性的转换，在折叠的过程中保持计算图的语义不发生改变。

\section{记忆优化}

属性求值贯穿于整个替换算法始终，一个替换规则中往往含有和模式图相同规模的属性表达式，一个属性表达式自身的结构可能也较为复杂，属性求值的执行时间也是不可忽视的。这些表达式中往往会有一些公共的部分，如果之前该公共的子表达式已经求出过值，那么下一次再求该表达式时，在满足一定条件时可以直接使用之前已求出的结果，而不需要再求一遍。这一方法称为记忆\cite{acar2003selective}（memoization），在函数式语言的优化中是一种重要的方法。本文中的属性表达式需要和模式表达式结合，和常规的函数式语言具有一定差异，所以在对其的记忆优化方法也需要结合其特点进行设计。

要进行优化，需要明确哪些表达式可以认为是公共的子表达式。本文中采用的是通过属性表达式AST对象的相等来确定：如果两个属性表达式是同一个对象，那么就认为是同一个表达式；否则，即使它们即使结构上等价，也不认为是同一个表达式。所基于的假设是如果一个属性表达式对象被多次引用，则其在定义过程中一定被绑定到某个Python局部变量上，那么该表达式一般会具有相对复杂的形式，之后再对该表达式求值时，直接从记录中取出会比直接求值效率更高。而如果一个表达式是就地构造的，可以认为其结构较为简单，此时应该直接求值，不需要考虑其是否和另一个表达式结构相同。通过值编号（Value Numbering)\cite{cocke1969programming}等方式可以分析出更多的公共子表达式，但这样不仅需要额外的分析过程，而且对提升计算表达式的求值效率提升不大，故没有采用。

在本文所描述的实现中，记忆仅用于改写阶段，而不用于匹配阶段。由\ref{sec:pat_attr_dep}节可知，属性表达式的求值依赖于模式表达式的匹配结果。在匹配阶段，需要进行若干匹配尝试，同一个属性表达式在不同匹配下求值的结果可能不同，这使得匹配阶段存储属性表达式的求值结果不具有太大价值。而在改写阶段，源模式的匹配关系已经确定。目标模式图要映射到计算图，其属性值只可能通过源计算图的属性值来求得，这使得属性表达式的求值相对固定，记忆已有的求值结果是有意义的。

除了模式匹配的结果外，环境$\Gamma$也会影响到属性表达式的求值结果。即使是同一个表达式，在不同环境下求出的值也可能不同。一个属性表达式如果含有不受约束的符号（称为自由符号），那么其取值就和求值环境相关。一个属性表达式的自由符号集合是其子表达式自由符号的并集再减去该属性表达式所绑定的符号。这是一个典型的数据流分析问题，只要对属性表达式的AST进行一次遍历即可得到结果。由于属性访问表达式中含有对模式表达式的引用，所以需要也对模式表达式进行类似的分析。如果一个属性表达式的自由符号集合为空，则该属性表达式的求值结果可以记忆。

\section{本章小结}

本章介绍了GSL的实现技术与方法。首先探讨了解决模式匹配与属性求值依赖关系的解决方法，并由此确定了语言的运行方式，介绍了对于单输出模式的匹配与改写算法。随后将匹配算法扩展到多输出顶点与可变输出顶点，详细地介绍了匹配此类模式算法的原理与方法。此外，本章也讨论了和语言实现相关的语义检查、记忆优化等技术问题。